#include <iostream>
#include <string>
#include <fstream>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <sstream>
#include <cfloat>

typedef std::vector<float> dimension_t;
typedef std::pair<float, dimension_t> value_t;
typedef std::string key_t;
typedef std::set<std::string> strset_t;

float get_distance(const dimension_t& dim1, const dimension_t& dim2);
bool is_converge(const std::vector<strset_t>& categories1,
		const std::vector<strset_t>& categories2);
void recacl_centroid(const std::map<key_t, value_t>& features,
		const std::vector<strset_t>& categories,
		std::vector<dimension_t> centroids);
void dispath_dim(const std::map<key_t, value_t>& features,
		std::vector<strset_t>& categories,
		const std::vector<dimension_t>& centroids);
void output_categories(const std::vector<strset_t>& categories, bool filter_single);

int main(void) {
	std::map<key_t, value_t> features;
	std::ifstream input;
	std::string line;

	input.open("feature_vector", std::ios_base::in);

	std::getline(input, line);
	while(!input.eof()) {
		std::string word;
		dimension_t items;
		int nDimesion = 0;
		float sum = 0.0;
		float item;

		std::stringstream ss;
		ss << line;

		ss >> word;
		ss >> item;
		while(!ss.eof()) {
			items.push_back(item);
			sum += item * item;
			nDimesion++;

			ss >> item;
		}

		features.insert(std::pair<key_t, value_t>(word,
					std::pair<float, dimension_t>(std::sqrt(sum), items)));

		std::getline(input, line);
	}

	input.close();

	int nDocument = features.size();
	int nCategory;

	std::cout << "Input the number of Categories(<=" << nDocument << "):"<< std::endl;
	std::cin >> nCategory;
	while(nCategory < 1 || nCategory >nDocument) {
		std::cout << "Please input valid number of Categories:";
		std::cin >> nCategory;
	}

	std::cout << "Filter Single?(yes/no):";
	std::string mode;
	std::cin >> mode;
	while(mode != "no" && mode != "yes") {
		std::cout << "Please input (yes/no):";
		std::cin >> mode;
	}

	//init centroids...
	std::vector<dimension_t> centroids;
	std::map<key_t, value_t>::iterator feature_itr;
	std::vector<strset_t> categories;	
	std::vector<strset_t> old_categories;
	strset_t strset;
	int i;
	for(i = 0, feature_itr = features.begin(); i < nCategory; i++, feature_itr++) {
		categories.push_back(strset);
		old_categories.push_back(strset);

		dimension_t dim;
		dim = feature_itr->second.second; 
		centroids.push_back(dim);
	}

ITERATE:
	dispath_dim(features, categories, centroids);

//	output_categories(categories);

	if(!is_converge(categories, old_categories)) {
		recacl_centroid(features, categories, centroids);
		old_categories = categories;

		std::vector<strset_t>::iterator cate_itr;
		for(cate_itr = categories.begin();
				cate_itr != categories.end();
				cate_itr++) {
			cate_itr->clear();
		}

		goto ITERATE;
	}

	output_categories(categories, mode == "yes");
	return 0;
}

void output_categories(const std::vector<strset_t>& categories, bool filter_single = true) {
	std::cout << "------------------------------" << std::endl << std::endl;
	for(int i = 0; i < categories.size(); i++) {
		const strset_t& cate = categories.at(i);
		if(filter_single && cate.size() == 1)
			continue;

		strset_t::const_iterator itr;
		for(itr = cate.begin();itr != cate.end(); itr++) {
			std::cout << *itr << "\t";
		}
		std::cout << std::endl << std::endl;
	}
}

float get_distance(const dimension_t& dim1, const dimension_t& dim2) {
	float sum1 = 0, sum2 = 0, x_sum = 0;
	for(int i = 0; i < dim1.size(); i++) {
		sum1 += dim1.at(i) * dim1.at(i);
		sum2 += dim2.at(i) * dim2.at(i);
		x_sum += dim1.at(i) * dim2.at(i);
	}

	sum1 = std::sqrt(sum1);
	sum2 = std::sqrt(sum2);
	
	return x_sum / (sum1 * sum2);
}

void dispath_dim(const std::map<key_t, value_t>& features,
		std::vector<strset_t>& categories,
		const std::vector<dimension_t>& centroids) {
	std::map<key_t, value_t>::const_iterator fea_itr;
	for(fea_itr = features.begin(); fea_itr != features.end(); fea_itr++) {
		const value_t& value = fea_itr->second;
		const dimension_t& dim = value.second; 
		float distance = 0;
		int idx = 0;

		std::cout << " word:" << fea_itr->first << std::endl;
		for(int i = 0; i < centroids.size(); i++) {
			const dimension_t& cent = centroids.at(i);
			float dist = get_distance(dim, cent);
			std::cout << dist << " " << distance << std::endl;
			if(dist > distance) {
				idx = i;
				distance = dist;
			}
		}

		categories.at(idx).insert(fea_itr->first);
	}

}

bool is_converge(const std::vector<strset_t>& categories1,
		const std::vector<strset_t>& categories2) {
	if(categories1.size() != categories2.size())
		return false;

	for(int i = 0; i < categories1.size(); i++) {
		const strset_t strset1 = categories1.at(i);
		const strset_t strset2 = categories2.at(i);

		if(strset1.size() != strset2.size())
			return false;

		strset_t::const_iterator itr1, itr2;
		for(itr1 = strset1.begin(), itr2 = strset2.begin();
				itr1 != strset1.end() && itr2 != strset2.end();
				itr1++, itr2++) {
			if(*itr1 != *itr2)
				return false;
		}
	}

	return true;
}

void recacl_centroid(const std::map<key_t, value_t>& features,
		const std::vector<strset_t>& categories,
		std::vector<dimension_t> centroids) {
	for(int i = 0; i < centroids.size(); i++) {
		dimension_t &cent = centroids.at(i);
		dimension_t::iterator itr;

		for(dimension_t::iterator itr = cent.begin();
				itr != cent.end(); itr++)
			*itr = 0;

		const std::set<std::string>& category = categories.at(i);
		std::set<std::string>::const_iterator word_itr;
		for(word_itr = category.begin();
				word_itr != category.end();
				word_itr++) {
			std::map<key_t, value_t>::const_iterator fea_itr;
			fea_itr = features.find(*word_itr);
			const dimension_t &dim = fea_itr->second.second;
			
			itr = cent.begin();
			dimension_t::const_iterator citr = dim.begin();
			for(;itr != cent.end() && citr != dim.end(); itr++, citr++) {
				*itr += *citr;
			}
		}

		for(itr = cent.begin();
				itr != cent.end(); itr++)
			*itr /= cent.size();
	}
}
